class Solution {
public:
    string reorganizeString(string s) {
        int n=s.size();
        unordered_map<char,int> hash;  
        for(int i=0;i<n;++i)
        {
            hash[s[i]]++;
        }
        auto cmp=[&](char a,char b){
            return hash[a]<hash[b];
        };
        string ret(n,' ');
        priority_queue<char,vector<char>,decltype(cmp)> q(cmp);
        for(auto ch:hash)
        {
            q.push(ch.first);
        }
        if(hash[q.top()]>(n+1)/2)
            return "";
        int index=0;
        while(q.size())
        {
            char k=q.top();
            q.pop();
            int count=hash[k];
            while(count-->0)
            {
                if(index>=n)
                    index=1;
                ret[index]=k;
                index+=2;
            }
        }
        return ret;
    }
};
